package gsw.tool.datastructure.tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

import gsw.tool.common.ToolShow;

/**
 * 二叉树
 *
 * @param <E>
 */
public class TreeBinary<E> {
    //前序遍历
    public static int PREORDER = 0;
    //中序遍历
    public static int INORDER = 1;
    //后序遍历
    public static int AFTERORDER = 2;
    //根节点
    Node<E> root;

    public static void test() {
        TreeBinary<String> tree = new TreeBinary<String>();
        tree.createData();

        tree.ergodicRecursion(tree.root, PREORDER);
        ToolShow.log("-------------------------------------");
        tree.ergodicRecursion(tree.root, INORDER);
        ToolShow.log("-------------------------------------");
        tree.ergodicRecursion(tree.root, AFTERORDER);
        ToolShow.log("-------------------------------------");

        tree.ergodicStack(tree.root, PREORDER);
        ToolShow.log("-------------------------------------");
        tree.ergodicStack(tree.root, INORDER);
        ToolShow.log("-------------------------------------");
        tree.ergodicStack(tree.root, AFTERORDER);
        ToolShow.log("-------------------------------------");
    }

    /**
     * 前序遍历
     */
    public void recursionPre() {
        ergodicRecursion(root, PREORDER);
    }

    /**
     * 中序遍历
     */
    public void recursionIn() {
        ergodicRecursion(root, INORDER);
    }

    /**
     * 后序遍历
     */
    public void recursionAfter() {
        ergodicRecursion(root, AFTERORDER);
    }

    /**
     * 递归遍历
     *
     * @param root 根节点
     * @param type 遍历方式：0代表前序，1代表中序，2代表后序
     */
    public void ergodicRecursion(Node<E> root, int type) {
        if (root == null) {
            return;
        }
        if (type == PREORDER) {
            ToolShow.log("前序：" + root.toString());
        }
        ergodicRecursion(root.left, type);
        if (type == INORDER) {
            ToolShow.log("中序：" + root.toString());
        }
        ergodicRecursion(root.right, type);
        if (type == AFTERORDER) {
            ToolShow.log("后序：" + root.toString());
        }
    }

    /**
     * 用栈遍历
     *
     * @param curr 当前节点
     * @param type 遍历方式：0代表前序，1代表中序，2代表后序
     */
    public void ergodicStack(Node<E> curr, int type) {
        //存放节点
        Stack<Node<E>> stack = new Stack<>();
        //记录已经添加过的节点
        List<Node<E>> nodeList = new ArrayList();
        stack.push(curr);
        nodeList.add(curr);
        while (curr != null) {
            //左子节点遍历完后，会回归一次；右子节点遍历完后，会回归一次；所以最多回归2次
            //第一次递归之前：只执行一次
            if (type == PREORDER && !nodeList.contains(curr.left) && !nodeList.contains(curr.right)) {
                ToolShow.log("前序：" + curr.data);
            }
            //相当于第一次递归:已经添加过的节点不能重复添加
            if (curr.left != null && !nodeList.contains(curr.left)) {
                curr = curr.left;
                stack.push(curr);
                nodeList.add(curr);
            } else {
                //第二次递归之前：只执行一次
                if (type == INORDER && !nodeList.contains(curr.right)) {
                    ToolShow.log("中序：" + curr.data);
                }
                //相当于第二次递归
                if (curr.right != null && !nodeList.contains(curr.right)) {
                    curr = curr.right;
                    stack.push(curr);
                    nodeList.add(curr);
                    //两次递归结束
                } else {
                    if (type == AFTERORDER) {
                        ToolShow.log("后序：" + curr.data);
                    }
                    stack.pop();
                    curr = stack.isEmpty() ? null : stack.lastElement();
                }
            }
        }
    }

    /**
     * 创建数据
     */
    public void createData() {
        Node<String> nodeB = new Node<String>("B");
        Node<String> nodeC = new Node<String>("C");
        Node<String> nodeD = new Node<String>("D");
        Node<String> nodeE = new Node<String>("E");
        Node<String> nodeF = new Node<String>("F");
        Node<String> nodeG = new Node<String>("G");
        Node<String> nodeH = new Node<String>("H");
        root = (Node<E>) new Node<String>("A");
        root.left = (Node<E>) nodeB;
        root.right = (Node<E>) nodeC;
        nodeB.left = nodeD;
        nodeB.right = nodeE;
        nodeC.right = nodeF;
        nodeF.left = nodeG;
        nodeF.right = nodeH;
    }

    /**
     * 二叉树的节点
     *
     * @param <E>
     */
    public static class Node<E> {
        public E data;
        //平衡因子
        public int bran;
        public Node<E> left;
        public Node<E> right;
        public Node<E> parent;

        public Node() {
        }

        public Node(E data) {
            super();
            this.data = data;
        }

        public Node(E data, int bran) {
            this.data = data;
            this.bran = bran;
        }

        @Override
        public String toString() {
            StringBuffer sb = new StringBuffer();
            sb.append("Node{" + data + ", bran=" + bran);
            if (left != null) {
                sb.append(", left=" + left.data);
            }
            if (right != null) {
                sb.append(", right=" + right.data);
            }
            if (parent != null) {
                sb.append(", parent=" + parent.data);
            }
            sb.append('}');
            return sb.toString();
        }
    }
}
